package cn.walls1717.leetcode.array;

/**
 * 904. 水果成篮
 * 力扣地址：https://leetcode-cn.com/problems/fruit-into-baskets/
 *
 * @author walls1717
 * @since 2022-05-08
 **/
public class T904 {

    public static void main(String[] args) {
        int[] fruits = {3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4};
        System.out.println(totalFruit(fruits));
    }

    /**
     * 滑动数组
     * 定义左指针 left和右指针 right，以及结果变量 ans，篮子数组 freq，水果种类数量变量 count
     * left固定位置，right先遍历，将 fruits 数组中的元素，放入下标
     * 为 fruits 元素的 freq数组中，在第一次放入一种水果
     * 的时候，count加 1，水果相同，就累加 freq 数组中的元素，将 ans 取最大值重新赋值
     * 当 count 大于 2 的时候，说明篮子中已经放入了两种水果，
     * 则遍历 left ，每移动一次 left，就将 freq 数组中对应的水果累减一个，
     * 直到减到 0，说明这个种类的水果在篮子里没有了，则 count 减 1，直到
     * 篮子中水果的种类小于等于2，再重新遍历 right，直到遍历完整个数组，
     * 取到最大的 ans
     *
     * @param fruits 数组
     * @return 结果
     */
    public static int totalFruit(int[] fruits) {
        int n = fruits.length;
        // 如果数组小于等于 2 ，说明所有种类的果子都可以装入篮子
        if (n <= 2) {
            return n;
        }
        /*
        ans：结果变量，初始值为 2 ，因为如果 <=2 在上面方法就已经结束
        初始值定义为 2 ，在接下来的程序中判断取最大值
        left：左指针，也就是慢指针
        right：右指针，也就是快指针
         */
        int ans = 2, left = 0, right = 0;
        // 存放果子的篮子
        int[] freq = new int[n];
        // 篮子中果子的种类数
        int count = 0;
        while (right < n) {
            /*
             这里是将 fruits 数组中的元素作为 freq 的下标
             在这个下标处，累加 1
             这样设计是根据题目中给出的提示 0 <= fruits[i] < fruits.length
             所以篮子的大小设置为 n 且这样设计程序不会发生数组越界
             */
            ++freq[fruits[right]];
            /*
             当 freq 数组中对应的元素变为 1 ，则表示添加了一种水果
             对应的 count 也要 ++
             如果不 == 1 了，那就说明是相同类型的水果放入篮子了
             */
            if (freq[fruits[right]] == 1) {
                ++count;
            }
            ++right;
            // 篮子中水果种类大于 2，直到篮子中水果的种类小于 2，数组滑动成功
            while (count > 2) {
                // 减掉左指针对应的水果
                --freq[fruits[left]];
                // 如果水果数量减到 0 了，那么这一种水果在篮子中就没有了，代表种类数量的 count 就要 --
                if (freq[fruits[left]] == 0) {
                    --count;
                }
                // 左指针前移
                ++left;
            }
            ans = Math.max(ans, right - left);
        }
        return ans;
    }
}
